/**
 * Created with IntelliJ IDEA.
 * Description:AVL树 插入操作
 * User: dings
 * Date: 2024-08-10
 * Time: 20:43
 */
public class AVLTree {
    public TreeNode root;
    static class TreeNode {
        public int val;//节点值
        public int bf;//平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父节点

        //构造方法
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            //首次插入时
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                //节点不能重复
                return false;
            }
        }
        //cur == null
        if (parent.val > val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        node.parent = parent;

        cur = node;
        //更新平衡因子
        while (parent != null) {
            if (parent.left == cur) {
                parent.bf--;
            }else {
                parent.bf++;
            }
            if (parent.bf == 0) {
                break;
            }
            if (parent.bf == 2 || parent.bf == -2) {
                if (parent.bf == -2) {
                    //左树高 --》 降低左树高度
                    if (cur.bf == -1) {
                        //右旋
                        rotateR(parent);
                    }else {
                        //左右双旋 cur.bf == 1
                        rotateLR(parent);
                    }
                }else {
                    //右树高
                    if (cur.bf == 1) {
                        //左旋
                        rotateL(parent);
                    }else {
                        //右左双旋 cur.bf = -1
                        rotateRL(parent);
                    }
                }
                //调整完成
                break;
            }
            cur = parent;
            parent = parent.parent;
        }
        return true;
    }


    /**
     * 右左双旋
     * @param parent：bf == 2的节点
     */
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateR(subR);
        rotateL(parent);

        if (bf == -1) {
            parent.bf = 0;
            subRL.bf = 0;
            subR.bf = 1;
        }else if (bf == 1) {
            parent.bf = -1;
            subRL.bf = 0;
            subR.bf = 0;
        }
        //注意这里没有修改bf == 0情况时的平衡因子，
        //是因为在上面进行双旋时平衡因子已经被修改好了
    }


    /**
     * 左右双旋
     * @param parent：bf == 2的节点
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        
        rotateL(subL);
        rotateR(parent);
        
        if (bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        } else if (bf == 1) {
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
        //注意这里没有修改bf == 0情况时的平衡因子，
        //是因为在上面进行双旋时平衡因子已经被修改好了
    }


    /**
     * 左单旋
     * @param parent：bf == 2的节点
     */
    private void rotateL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        //进行连接关系的修改，完成旋转操作
        subR.left = parent;
        parent.right = subRL;
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if (subRL != null) {
            //只有subRL不为空时才可访问
            subRL.parent = parent;
        }
        //旋转前parent可能具有父节点，需要修改subR的父亲指向
        subR.parent = pParent;
        if (pParent != null) {
            if (parent == pParent.left) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
        }else {
            //parent为根节点时
            root = subR;
        }
        //修改平衡因子
        parent.bf = 0;
        subR.bf = 0;
    }


    /**
     * 右单旋
     * @param parent：bf == 2的节点
     */
    private void rotateR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        //进行连接关系的修改，完成旋转操作
        parent.left = subLR;
        subL.right = parent;
        if (subLR != null) {
            //只有subLR存在时才可访问
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //旋转前parent可能具有父节点，需要修改subR的父亲指向
        subL.parent = pParent;
        if (pParent != null) {
            if (pParent.left == parent) {
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
        }else {
            //parent为根节点时
            root = subL;
        }
        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }

    /**
     * 中序遍历 --》 判断是否为二叉搜索树
     * @param root
     */
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }

    /**
     * 求树的高度
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);

        return Math.max(leftH,rightH)+1;
    }

    public boolean isBalance(TreeNode root) {
        if (root == null) {
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        //平衡因子就是 错 的情况下
        if (root.bf != rightH-leftH) {
            return false;
        }

        //根节点和左右子树都要平衡
        return leftH-rightH <= 1 && isBalance(root.left) && isBalance(root.right);
    }
}
